// https://leetcode.cn/problems/evaluate-reverse-polish-notation/
// Created by ade on 2022/8/19.
//
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;

class Solution {
public:
    int evalRPN(vector <string> &tokens) {
        vector <string> st;
        for (auto t : tokens) {
            if (!isOperator(t)) {
                st.push_back(t);
                continue;
            }
            int t1 = stoi(st.back());
            st.pop_back();
            int t2 = stoi(st.back());
            st.pop_back();
            switch (t[0]) {
                case '+':
                    st.push_back(to_string(t2 + t1));
                    break;
                case '-':
                    st.push_back(to_string(t2 - t1));
                    break;
                case '*':
                    st.push_back(to_string(t2 * t1));
                    break;
                case '/':
                    int res = t2 / t1;
                    st.push_back(to_string(res));
                    break;
            }
        }
        return stoi(st.back());
    }

    bool isOperator(string s) {
        return s == "+" || s == "-" || s == "*" || s == "/";
    }
};

int main() {
    Solution so;
    vector <string> nums = {"2", "1", "+", "3", "*"};
    cout << so.evalRPN(nums) << endl;
    return 0;
}